//
// author: alexander van renen
// date: 26.01.2011
// purpose: ...
//
// notice 1 - resource managing class:
//        take a look at the FragmentResourceManager class 
//        which makes it realy easy to not mess up the heaps
//        its destructor will automatically free the allocated
//        memory and i didnt had to take care of calling free
//        at every potential exit point of the program.
//        but to be fair i extended the functinallity of the
//        class a bit ;)
//
// notice 2 - valgrind and string len
//        it does not seem to work well together. i always got
//        a "Conditional jump or move depends on uninitialised
//        value(s)" error by valgrind. now i replaced the c-lib
//        version of strlen by my own version (just brute force)
//
/////////////////////////////////////////////////////

#include <iostream>
#include <fstream>
#include <string.h>
#include <stdio.h>


class FragmentReassembler {
	
	public:
		
		FragmentReassembler()
		: fragments(NULL)
		, numElements(-1)
		, maxNumElements(-1)
		{}
		
		~FragmentReassembler() {
			
			for(unsigned int i=0; i<=numElements && i<maxNumElements; i++) {
				
				if(fragments[i] == NULL) {
					
					numElements++;
					continue;
				}
				
				delete [] fragments[i];
			}
			
			if(maxNumElements != -1)
				delete [] fragments;
		}
		
		bool createFragmentsFromFile(char* fileName) {
		
			//open and check ifstream
			std::ifstream input(fileName, std::ios::binary);
			if(!input.good()) {
				
				std::cout << "unable to open file, please check if the file exists" << std::endl;
				return false;
			}
			
			//read and check number of fragments
			input >> maxNumElements;
			if(!input.good()) {
				
				maxNumElements= -1; //making sure that free is not called on unallocated memory
				std::cout << "malformed file - it is required that there is an integer at the begin of the file" << std::endl;
				return false;
			}
			
			fragments= new char*[maxNumElements];
			
			//read fragments
			char buffer[1001];
			//memset(buffer, 0, 1001); //needed by stupid valgrind
			
			while(input.good()) {
				
				//eliminate the begin '#'
				if(!removePound(&input)) return false;
				if(input.eof()) break;
				
				input.get(buffer, 1001, '#');
				
				add(&buffer[0]);
				if(numElements > maxNumElements) {
					
					std::cout << "malformed file - the number at the begin of the file which specified the number of fragments was wrong" << std::endl;
					return false;
				}
				
				//eliminate the ending '#'
				if(!removePound(&input)) return false;
			}
			
			return numElements+1==maxNumElements;
		}
		
		char* reassemble()
		{
			std::cout << maxNumElements << std::endl;
			char* result;
			for(int i=0; i<maxNumElements-1; i++) {
				
				int pos1= -1;
				int pos2= -1;
				
				OverlappingInfo bestFitt;
				//find the one
				for(int j=0; j<maxNumElements; j++) {
					
					if(fragments[j] == NULL) continue;
					for(int k=j; k<maxNumElements; k++) {
						if(fragments[k] == NULL) continue;
						if(j == k) continue;
						
						OverlappingInfo tmpFitt(fragments[j], fragments[k], 0);
						findMaxOverlap(&tmpFitt);
						if(tmpFitt.numOverlapping >= bestFitt.numOverlapping) {
							
							bestFitt= tmpFitt;
							pos1= k;
							pos2= j;
							
						}
					}
				}
				
				result= merge(&bestFitt);
				delete [] fragments[pos1];
				delete [] fragments[pos2];
				fragments[pos1] = NULL;
				fragments[pos2] = result;
				numElements--;
			}
			
			return result;
		}
		
	private:
		
		char** fragments;
		unsigned int numElements;
		unsigned int maxNumElements;
		
		struct OverlappingInfo {
			
			OverlappingInfo(const char* first=NULL, const char* second=NULL, int numOverlapping=0)
			: first(first), second(second), numOverlapping(numOverlapping)
			{}
			
			const char* first;
			const char* second;
			int numOverlapping;
		};
		
		struct Fragment {
			
			Fragment(char* s, int length) : s(s), length(length) {}
			~Fragment() {delete s;}
			char* s;
			unsigned int length;
		};
		
		static bool removePound(std::ifstream* input) {
			
			char poundCatcher= input->get();
			if(poundCatcher != '#' && input->peek() != -1) {
				
				std::cout << "malformed file - the fragments have to be encapsulated by # at the begin and at the end" << std::endl;
				return false;
			}
			return true;
		}
		
		void add(char* buffer) {
			
			numElements++;
			
			//this one works
			int length= strlen(buffer);
			length = length+1;
			int offset = (4-(length)%4 == 4) ? 0 : (4-(length)%4);
			length+= offset;
			char* heapBuffer= new char[length];
			memset(heapBuffer, 0, length);
			strcpy(heapBuffer, buffer);
			fragments[numElements]= heapBuffer;
			
			return;
		}
		
		inline int getNumOverlappingChars(const char* lhs, const char* rhs)
		{
			
			int count = 0;
			while(*lhs!='\0' && rhs!='\0' && *lhs == *rhs) {
				count++;
				rhs++;
				lhs++;
			}
			return count;
		}
		
		void findMaxOverlap(OverlappingInfo* oli)
		{
			
			int firstLength = strlen(oli->first);
			int secondLength = strlen(oli->second);
			
			//swap so that second argument is the shorter string
			if(secondLength > firstLength) {
				
				int tmpLength = firstLength;
				firstLength = secondLength;
				secondLength = tmpLength;
				
				const char* tmpBase = oli->first;
				oli->first = oli->second;
				oli->second= tmpBase;
			}
			
			const char* localFirst = oli->second;
			const char* localSecond = oli->first;
			
			//try to find oli->second inside of the oli->first sting
			for(int i=0; i<=firstLength-secondLength; i++, localSecond++) {
				
				if(getNumOverlappingChars(localSecond, localFirst) == secondLength) {
					oli->numOverlapping = secondLength;
					return; //found complete cover more is impossible
				}
			}
			
			//this loop continues the second loop
			//but now the oli->second is not completety inside the oli->first ..
			for(int i=firstLength-secondLength+1; i<=firstLength; i++, localSecond++) {
				
				int overlapping = getNumOverlappingChars(localSecond, localFirst);
				if(overlapping == firstLength - i) {
					oli->numOverlapping = overlapping;
					break;
				}
				
			}
			
			//now checking the begin of the first sting
			for(int i=0; i<=secondLength; i++, localFirst++) {
				
				int overlapping = getNumOverlappingChars(oli->first, localFirst);
				
				if(secondLength-i < oli->numOverlapping)
					break;
				
				if(overlapping == secondLength-i) {
					
					const char* tmpBase = oli->first;
					oli->first = oli->second;
					oli->second = tmpBase;
					oli->numOverlapping = overlapping;
					break;
				}
			}
			
			return;
		}
		
		char* merge(OverlappingInfo* info)
		{
			
			int firstLength = strlen(info->first);
			int secondLength = strlen(info->second);
			
			int mergedLength = firstLength + secondLength - info->numOverlapping;
			
			char* mergedStr = new char[mergedLength+1];
			
			memcpy(mergedStr, info->first, firstLength);
			if(info->numOverlapping != secondLength)
				memcpy(mergedStr+firstLength-info->numOverlapping, info->second, secondLength);
			mergedStr[mergedLength] = '\0';
			
			return mergedStr;
		}
};

int main(int argc, char* argv[])
{
	
	//check arguments
	if( argc != 2) {
		
		std::cout << "wrong number of arguments, you have to specify a filename and thats it." << std::endl;
		return -1;
	}
	
	FragmentReassembler fragments;
	
	if(!fragments.createFragmentsFromFile(argv[1])) {
		
		return -1;
	}
	
	std::cout << fragments.reassemble() << std::endl;
	
	return 0;
}